package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/8/11.<br><br>
 *
 * 中等：找树左下角的值
 */
public class Topic513 {

    public static void main(String[] args) {
        Topic513 instance = new Topic513();

        List<Integer> list = Arrays.asList(2,1,3);
        TreeNode root = Util.createTree(list);
        System.out.println(instance.findBottomLeftValue(root));

        list = Arrays.asList(1,2,3,4,null,5,6,null,null,null,null,7);
        root = Util.createTree(list);
        System.out.println(instance.findBottomLeftValue(root));
    }

    public int findBottomLeftValue(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        helper(root, list, 0);
        return list.get(list.size() - 1);
    }

    private void helper(TreeNode root, List<Integer> list, int depth) {
        if(root == null) {
            return ;
        }

        if(depth == list.size()) {
            list.add(root.val);
        }

        helper(root.left, list, depth + 1);
        helper(root.right, list, depth + 1);
    }
}
